#include <stdio.h>
#include <stdlib.h>

int MSearch(int A[] , int B[],int n ) {
    int s1 = 0, d1 = n-1, m1, s2 = 0, d2 = n-1, m2;
    //分别表示序列A 和B 的首位数、末位数和中位数
    while(s1 != d1 || s2 != d2) {
        m1=(s1+d1)/2 ;
        m2=(s2+d2)/2 ;
        if (A[m1] == B[m2])
            return A[m1]; //满足条件①
        if (A[m1] < B[m2] ) { //满足条件②
            if((s1 + d1)% 2==0){//若元素个数为奇数
                s1 = m1; //舍弃A 中间点以前的部分且保留中间点
                d2 = m2; //舍弃B 中间点以后的部分且保留中间点
            }else{ //元素个数为偶数
                s1 = m1+1; //舍弃A 中间点及中间点以前部分
                d2 = m2; //舍弃B 中间点以后部分且保留中间点
            }
        }
        else{ //满足条件③
            if ((s2+d2) %2==0 ) { //若元素个数为奇数
                d1=m1; //舍弃A 中间点以后的部分且保留中间点
                s2=m2; //舍弃B 中间点以前的部分且保留中间点
            }else{ //元素个数为偶数
                d1=m1 ; //舍弃A 中间点以后部分且保留中间点
                s2=m2+1; //舍弃B 中间点及中间点以前部分
            }
        }
    }
    return A[s1]<B[s2]? A[s1]:B[s2];
}

int main(){
    int A[] = {11,12,13,16,17};
    int B[] = {8,9,10,14,15};
    printf("median is :%d\n", MSearch(A,B,5));
    system("pause");
}
